package heap;

import java.io.File;
import java.io.FileNotFoundException;
import java.util.ArrayList;
import java.util.Scanner;

public class ReplacementHeap {
	private int heapSize;
	private int n;
	private int deadSpace;
	private int[] heapWithDeadSpace;
	ArrayList<Integer> input = new ArrayList<Integer>();
	ArrayList<Integer> output = new ArrayList<Integer>();
	private int runs = 1;

	public ReplacementHeap(int n) {
		this.heapSize = n;
		this.n = n;
		heapWithDeadSpace = new int[n];
	}

	public void buildInput(File file) {
		Scanner scanner = null;
		try {
			scanner = new Scanner(file);
			while (scanner.hasNextInt()) {
				input.add(scanner.nextInt());
			}
		} catch (FileNotFoundException e) {
			e.printStackTrace();
		} finally {
			scanner.close();
		}
	}

	public void insert(int number) {

	}

	public int[] test() {
		for (int i = 0; i < heapSize; i++) {
			heapWithDeadSpace[i] = input.remove(0);
		}
		return heapWithDeadSpace;
	}

	public int[] getHeap() {
		return heapWithDeadSpace;
	}

	private void percolateUp(int place) {
		while (heapWithDeadSpace[place] <= heapWithDeadSpace[place / 2] && place != 0) {
			int temp = heapWithDeadSpace[place];
			heapWithDeadSpace[place] = heapWithDeadSpace[place / 2];
			heapWithDeadSpace[place / 2] = temp;
			place = place / 2;
		}
	}

	public void percolateDown(int place) {

		while (true) {

			int leftChildIndex = leftChildOf(place);
			int rightChildIndex = rightChildOf(place);

			boolean hasRightChild = true;

			if (leftChildIndex >= heapSize)
				break;

			if (rightChildIndex >= heapSize)
				hasRightChild = false;

			if (heapWithDeadSpace[leftChildIndex] < heapWithDeadSpace[place]
					|| (hasRightChild && heapWithDeadSpace[rightChildIndex] < heapWithDeadSpace[place])) {

				int smallestChildIndex = (!hasRightChild || heapWithDeadSpace[leftChildIndex] < heapWithDeadSpace[rightChildIndex]) ? leftChildIndex
						: rightChildIndex;

				int tempIndexValue = heapWithDeadSpace[place];
				heapWithDeadSpace[place] = heapWithDeadSpace[smallestChildIndex];
				heapWithDeadSpace[smallestChildIndex] = tempIndexValue;

				place = smallestChildIndex;

			} else {
				break;
			}
			// System.out.println(toString());

		}
	}

	private int rightChildOf(int index) {
		return leftChildOf(index) + 1;
	}

	private int leftChildOf(int index) {
		return (index + 1) * 2 - 1;
	}

	public void buildHeap() {
		for (int i = 0; i < heapSize; i++) {
			percolateUp(i);
		}
	}

	public void run() {
		// read N elements from input into heap[]
		for (int i = 0; i < n; i++) {
			heapWithDeadSpace[i] = input.remove(0);
		}

		// inital build heap
		buildHeap();

		// until all input is read
		while (!input.isEmpty()) {

			// write smallest to output
			int smallest = heapWithDeadSpace[0];
			output.add(smallest);

			int next = input.remove(0);

			System.out.println(this + " out: " + heapWithDeadSpace[0] + " next: " + next);

			if (next >= smallest) {
				heapWithDeadSpace[0] = next;
				percolateDown(0);
			} else {

				percolateUp(heapSize - 1);

				heapSize--;
				deadSpace++;
				int deadSpaceIndex = heapWithDeadSpace.length - deadSpace;

				heapWithDeadSpace[0] = heapWithDeadSpace[deadSpaceIndex];
				percolateDown(0);

				heapWithDeadSpace[deadSpaceIndex] = next;
			}

			if (heapSize == 0) {
				runs++;

				heapSize = n;
				deadSpace = 0;
				buildHeap();
				System.out.println("End of run, rebuild heap");
			}

		}

		System.out.println("Heap: " + this);

		for (int i = 0; i < heapSize; i++) {
			output.add(heapWithDeadSpace[i]);
		}

		if (deadSpace > 0) {

			runs++;

			for (int i = 0; i < deadSpace; i++) {
				heapWithDeadSpace[i] = heapWithDeadSpace[heapSize + i];
			}

		}

		heapSize = deadSpace;
		deadSpace = n - heapSize;

		buildHeap();

		for (int i = 0; i < heapSize; i++) {
			output.add(heapWithDeadSpace[i]);
		}

		System.out.println("Output: " + output + "\nDeadspace: " + deadSpace + "\nHeapsize: " + heapSize);

		System.out.println("Runs: " + runs);

	}

	@Override
	public String toString() {
		String s = "[";
		for (int i = 0; i < heapWithDeadSpace.length; i++) {
			s += heapWithDeadSpace[i];

			if (i >= heapSize)
				s += "*";

			if (i < heapWithDeadSpace.length - 1)
				s += ",";
		}
		s += "]";
		return s;
	}
}
